/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package open.algo.sort;

/**
 *
 * @author lee
 */
public class HeapSort implements Sort
{

    /**
     * 1. find the max(a[i], a[i*2], a[i*2 + 1]
     * 2. if a[i] is not max
     * 2.1 -- exchange a[i] <-> min
     * 2.2 -- adjustHeap(a, i * 2, heapSize)
     * 
     * @param a
     * @param i
     * @param heapSize
     */
    private void adjustHeap(int[] a, int i, int heapSize)
    {
        int j = (i << 1) + 1;
        int v = a[i];
        while (j < heapSize)
        {
            if (j + 1 < heapSize && a[j] <= a[j + 1])
            {
                j++;
            }
            if (v >= a[j])
            {
                break;
            }

            a[i] = a[j];

            i = j;
            j = (i << 1) + 1;
        }

        a[i] = v;
    }

    /**
     * 1. for i = [0, (length -1)/2]
     * 1.1 -- adjustHeap(a, i, length-1);
     * @param a
     */
    private void buildHeap(int[] a)
    {
        for (int i = (a.length - 1) >> 1; i >= 0; i--)
        {
            adjustHeap(a, i, a.length);
        }
    }

    /**
     * 1. build heap
     * 2. for i = [n-1, 1]
     * 2.1 -- exchange a[0] <-> a[i]
     * 2.2 -- adjustHeap(a, 0, i);
     *
     * 
     * @param a
     */
    @Override
    public void sort(int[] a)
    {
        buildHeap(a);
        int temp = 0;
        for (int i = a.length - 1; i > 0; i--)
        {
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            adjustHeap(a, 0, i);
        }
    }

    public static void main(String[] args)
    {
        SortTest test = new SortTest();
        int[] a = test.getArray();
        Sort sort = new HeapSort();
        sort.sort(a);
        SortTest.print(a);
    }
}
